package program.leetcode.array;

import java.util.*;

/**
 * 给定两个数组，编写一个函数来计算它们的交集。
 * 若两个数组中出现重复的次数一致, 那么可以输出多个重复的数据.
 *
 * 解法:
 *  1. 先得到最小的数组。
 *  2. 把最小数组的数字和数字出现的次数存入map中<num, count>.
 *  3. 遍历第二个数组, 对于每个数字对在map中进行查找.
 *  4. 然后相应的次数减少1, 因为可能num2中存储同一个数字的重复.
 *  5. 使用了nums1的空间, k为有效数据的最大范围.
 */
public class leetCode_350 {

    private static int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }

        HashMap<Integer, Integer> m = new HashMap<>();
        for (int n : nums1) {
            m.put(n, m.getOrDefault(n, 0) + 1);
        }
        int k = 0;
        for (int n : nums2) {
            int cnt = m.getOrDefault(n, 0);
            if (cnt > 0) {
                nums1[k++] = n;
                m.put(n, cnt - 1);
            }
        }
        return Arrays.copyOfRange(nums1, 0, k);
    }

    private static int[] test(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            test(nums2, nums1);
        }

        Map<Integer, Integer> map = new HashMap<>(nums1.length);
        for (int item : nums1) {
            map.put(item, map.getOrDefault(item, 0) + 1);
        }

        int k = 0;
        for (int item : nums2) {
            Integer cnt = map.getOrDefault(item, 0);
            if (cnt > 0) {
                nums1[k++] = item;
                map.put(item, cnt - 1);
            }
        }

        return Arrays.copyOfRange(nums1, 0, k);
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 2, 4, 4};
        int[] nums2 = {2, 2, 4, 4};
        int[] result = test(nums, nums2);
        for (int item : result) {
            System.out.println(item);
        }
    }
}
